public class Main {
    /*
     * 腐烂的橘子
     *
     *
     * */
    static class Pair{
        int x;
        int y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return x == pair.x &&
                    y == pair.y;
        }
        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    public int BFS(HashMap<Pair, Integer> map, int row, int col) {
        //标记时间
        int times = 0;
        //标记方向数组
        int[][] nextP = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        //队列
        Queue<Pair> queue = new LinkedList<>();
        //找到最先腐烂的橘子
        for (Map.Entry<Pair, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 2) {
                queue.offer(entry.getKey());
                int x = entry.getKey().x;
                int y = entry.getKey().y;
            }
        }
        //如果没有好的橘子，不必浪费时间
        if (!map.containsValue(1)) {
            return 0;
        }

        while (!queue.isEmpty()) {
            int size = queue.size();
            //当前一批腐烂的橘子 带出下一批腐烂的橘子
            for (int i = 0; i < size; i++) {
                Pair pair = queue.poll();
                for (int[] next : nextP) {
                    int newX = pair.x + next[0];
                    int newY = pair.y + next[1];
                    if (newX >= row || newX < 0 || newY >= col || newY < 0) {
                        continue;
                    }
                    Pair curP = new Pair(newX, newY);
                    if (map.get(curP) == 1) {
                        map.put(curP, 2);
                        queue.offer(curP);
                    }
                }
            }
            times++;
            if (!map.containsValue(1)) {
                return times;
            }
        }
        return -1;
    }

    public int orangesRotting(int[][] grid) {
        HashMap<Pair, Integer> map = new HashMap<>();
        int row = grid.length;
        int col = grid[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                map.put(new Pair(i, j), grid[i][j]);
            }
        }
        return BFS(map, row, col);
    }


    /*
     * 腐烂的橘子2
     * 用flag标记当前一批腐烂的橘子，有没有传染其他的橘子；如果传染的话，传染时间一分钟，times++；如果没有传染的话，说明不会再传染了，此时的time就固定了
     * */
    public int orangesRotting2(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        Queue<Pair> queue = new LinkedList<>();

        //找到最先腐烂的橘子
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new Pair(i, j));
                }
            }
        }
        //标记时间
        int times = 0;
        //方向数组
        int[][] nextP = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        //开始BFS
        while (!queue.isEmpty()) {
            int size = queue.size();
            int flag = 0;
            //当前一批（一层）腐烂的橘子 带出 下一批要腐烂的橘子
            for (int i = 0; i < size; i++) {
                Pair pair = queue.poll();
                //向四个方向延伸
                for (int[] next : nextP) {
                    int newX = pair.x + next[0];
                    int newY = pair.y + next[1];
                    if (newX >= row || newX < 0 || newY >= col || newY < 0) {
                        continue;
                    }
                    if (grid[newX][newY] == 1) {
                        grid[newX][newY] = 2;
                        //新腐烂的橘子入队列
                        queue.offer(new Pair(newX, newY));
                        //有新橘子腐烂
                        flag = 1;
                    }
                }
            }
            if (flag == 1) {
                times++;
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return times;
    }
}